This application is directed to graph searching in the planning area, and more particularly planning in non-deterministic environments, which arise in many real-world applications, including business process management (BPM).
Graph searching accounts for much of the heavy-lifting in many areas of high performance computing and artificial intelligence (AI), such as planning, scheduling, combinatorial optimization, and model checking. This is because these tasks generally include searching graphs having exponential size in the depth of the search. Thus, finding an optimal or even approximate solution can take a long time, and the ability to scale up to larger problems is to a large degree dependent on the speed of the underlying graph-search algorithm.
Different planning categories exist in the planning area including classical planning and non-deterministic planning. Classical planning generates a linear sequence of actions which move towards a final goal. Non-deterministic planning differs from classical planning in that a single action can result in one of many outcomes that are beyond the control of the decision maker. As a result, the solution to a nondeterministic planning problem (i.e., a plan) is no longer a linear sequence of actions but rather it takes the form of a tree or a graph. Correspondingly, the search space of a non-deterministic planning problem must be enriched with new types of search nodes called AND nodes that correspond to multiple outcomes which all need to be reasoned about, in addition to the OR nodes (corresponding to agent's options) that are commonly found in the search space of classical planning problems.
Graphs are used to represent problems and are employed to find solutions to problems, wherein finding a path through a graph represents a solution to a represented problem. A variety of different graph search techniques exist to find a solution or path depending on the type of problem or type of graph used to represent the problem. Historically, graphs focused on the best solution or shortest path in a graph, wherein a value of a solution or path through the graph is defined by costs to obtain the solution or path. The costs of various potential solutions or paths may then be compared to select a specific solution or path. Costs are estimated initially and, with an admissible cost estimator, are never overestimated, but can be updated as the graph is expanded and more information becomes available.
FIG. 1 shows an example of an AND/OR search graph 100 with two actions a1 and a2. The start state of the search graph is an OR node with two outgoing arcs that correspond to actions a1 and a2 for which the planner can choose one of them. Each arc from the start state leads to an AND node with two successor OR nodes, one for each possible outcome state. By convention, a square denotes an OR node (or a choice node) and a circle denotes an AND node (or a chance node) resulted from the nondeterministic outcomes of a1 or a2. A full contingency plan must specify the action to take under all possible outcomes or contingencies as a result of executing the plan. A k-connector connects a state to a set of k successor states, one for each possible immediate outcome. A solution to an AND/OR search problem takes the form of an acyclic graph called the solution graph with the following properties:                The start state is part of the solution graph        For any non-goal state, only one outgoing k-connector is part of the solution graph and each of its successor states is also part of the solution graph        
If every path in the solution graph eventually ends at a goal state, then the plan is called a strong plan. If some but not all paths terminate at a goal state, the plan is called a weak plan. A strong plan guarantees that the goal state is reached no matter what happens; whereas a weak plan does not. Whether a planning problem admits a strong or weak plan depends on (a) the set of operators that transform one state into another, (b) the starting state, and (c) the goal state. While strong plans are generally preferred over weak plans, there are exceptions in applications such as business process management (BPM), in which shorter weak plans can sometimes be more desirable than strong plans that are much longer.
As problems and graphs have become more complex, parallelism has been added to reduce the time to solve a problem. Computer applications operating on electronic computing devices use graphs by constructing a graph representing a problem, and then employ an algorithm to search the graph for a solution. Typically these are done simultaneously. Node expansion dynamically constructs a graph with some initial starting state. Searching the graph is done as the graph is constructed in order to find a solution, but such searching must consider whether there are cycles or redundancies in the graph.
AND/OR graph search problems can be solved by the AO* algorithm, which constructs an explicit search graph that initially consists of the start state and is gradually expanded by the following algorithmic steps:    1. Find the best non-goal leaf node by following the best action at each OR node until a non-goal leaf node is reached.    2. Expand the best non-goal leaf node by generating its successors and adding any new successor states to the explicit search graph. For each new state s, set f(s)=h(s) where h(s) is an admissible heuristic that never overestimates the cost of reaching a goal state from s.    3. Recursively update the cost function (f-cost) of the ancestor nodes of the just-expanded state until the start state is reached and mark the best action for each ancestor state encountered along the way. To update the f-cost of a state s, set f(s)=mins′[c(s, s′)+f(s′)] where s′ is a successor state of s and c(s, s′) is the cost of going from state s to state s′. The action that takes s to its best successor, argmins′[c(s, s′)+f(s′)], is marked as the best action for state s (where argmins stands for the arguments of the minimum).
AO* repeats the above steps until all leaf nodes reachable by following the best actions are all goal nodes. More precisely, the termination condition of AO* is defined as follows:                a. An OR node is solved if it is a goal node, or one of its children is solved; otherwise it is failed.        b. An AND node is solved if all of its children are solved; otherwise it is failed.        c. AO* terminates when the start state is solved or failed.        
A variant of the AO* algorithm attempts to address weak plans (i.e., plans that are not guaranteed to reach a goal node under all circumstances) by modifying the definition of step b in the AO* termination condition as follows:                b′. An AND node is solved if all of its children are either solved or failed, and at least one child is solved; otherwise it is failed.        
The above definition of b′ seeks to accommodate weak plans for BPM in AO* search, where strong plans are either infeasible or too expensive to compute or execute. In BPM planning, the response time is of importance, as the planner must interact with the business user in real time or semi real-time (subject to human patience). Thus, fast planning is deemed as a major requirement for automated planning to be practical in BPM. However, since the speed of a single processor core is not expected to improve dramatically over time, efficient parallelization of AO* and its variants on multiple cores or computers is the only way to significantly improve their speed.
Keeping track of all possible action outcomes in a non-deterministic environment can lead to a combinatorial explosion of the search space. Therefore, a parallel AO* (or PAO*) search technique has been developed to increase the speed of finding a solution through parallelism. This technique uses a master-worker scheme where a master assigns work to workers which work in parallel. Specifically:    1. The master process searches from the root node in a sequential manner until the explicit search graph constructed is sufficiently large.    2. The master process divides up the parallelization frontier, which represents the fringe of the explicit search graph, and distributes them as sub-problems to workers for concurrent solving.    3. Workers solve their assigned sub-problems in parallel using sequential AO* and transmit the optimal sub-problem solution back to the master process.    4. The master process combines the solutions from all the workers to obtain the overall solution.
The difficulty with this technique when trying to be put into practice includes the determination of when the explicit search graph is sufficiently large and building of the graph may be stopped (Step 1) and sub-problems may start to be distributed to workers (Step 2). Another issue is if there are redundant parts of the search space that multiple workers may visit how to coordinate search efforts to minimize repeated work between workers.
As to the first issue, there is a trade-off between the size of the initial search graph and the size of the sub-problems: if the parallelization frontier is too small, it will result in only a few sub-problems that are too complex for the workers to solve quickly. On the other hand, an overly large parallelization frontier will lead to many small and sometimes trivial sub-problems to be generated and passed on to the workers, which will add significant communication overhead to defeat any parallel speedup achieved at the individual worker level. With regard to the second issue, sparse inter-worker communication is usually preferred, but the price paid is an increased amount of redundant search due to a lack of timely communication. Such an increase is in worst case exponential in the depth of search, which usually wipes out any parallel speedup gains, since at best the number of processor cores or machines are only a polynomial resource in most practical settings.